package offer.day28;

public class No47GetMaxValue {
    /*
     * 面试题47：礼物的最大价值
     * 题目：在一个m*n的棋盘的每一个都放有一个礼物，每个礼物都有一定的价值（价值大于0）.
     * 可以从棋盘的左上角开始拿格子里的礼物，并每次向左或者向下移动一格，直到到达期盼的右下角。
     * 给定一个棋盘以及上面的礼物，请计算最多能拿到多少价值的礼物？
     *
     * 思路:运用动态规划思想，f(i,j)=max{f(i-1,j),f(i,j-1)}+values(i,j)
     * f(i,j)表示到达(i,j)格子是能拿到的礼物总和的最大值
     * 用辅助的数组来保存中间计算结果
     *其中辅助数组不用和m*n的二维数组一样大，只需要保存上一层的最大值就可以了
     *使用长度为列数n的一维数组作为辅助数组
     *
     * https://www.cnblogs.com/yongh/p/9950556.html
     * 其中注意：
     * 1>动态规划问题，使用公式表示其中的关系
     * 2>当动态规划中有大量重复计算，可以使用循环和辅助空间来提高效率
     * 3>若是遇到需要对中间结果进行保存的问题的时候，可能能否游湖辅助空间（二维数组----->一维数组空间）
     * */
    public static void main(String[] args) {
        int[][] values = {{1,10,3,8},{12,2,9,6},{5,7,4,11},{3,7,16,5}};
        No47GetMaxValue g = new No47GetMaxValue();
        System.out.println("最多能拿到"+g.GetMaxValue(values)+"价值的礼物！！！");
    }

    private int GetMaxValue(int[][] values) {
        int m=values.length;
        int n=values[0].length;
        int[][] dp=new int[m][n];
        dp[0][0]=values[0][0];
        for(int i=1;i<m;i++){
            dp[i][0]=dp[i-1][0]+values[i][0];
        }
        for(int j=1;j<n;j++){
            dp[0][j]=dp[0][j-1]+values[0][j];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+values[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}
